home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_11_08 / 1108036b < prev    next >
Text File  |  1993-05-03  |  23KB  |  582 lines
  1. /***************************************************************
  2.  * file: ZONE.C
  3.  * purpose: text region detection via cellular automata
  4.  **************************************************************/
  5.  
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <string.h>
  9. #include <errno.h>
  10. #include "zone.h"
  11.  
  12. /* local data */
  13. static ZONE zone_list[MAX_ZONES];   /* this could be dynamically allocated */
  14. static int zone_count;
  15.  
  16.  
  17. /* local prototypes */
  18. static unsigned char *sample_page(int *dx,int *dy,int *samplex,int *sampley);
  19. static void cut_vertical_lines(unsigned char *image,int dx,int dy);
  20. static void block_zones(unsigned char *image,int dx,int dy,int coarseness);
  21. static void sequence_zones(unsigned char *image,int dx,int dy,int order);
  22. static int extract_zone(unsigned char *image,int dx,int dy,int x,int y,ZONE *zone_ptr);
  23. static void overlap_zones(ZONE *zone_array,int *array_size);
  24.  
  25.  
  26. /************************************************
  27.  * function: int zone(int coarseness)
  28.  *  The process steps are:
  29.  *      1) Sample the page
  30.  *      2) Cut vertical lines from the page
  31.  *      3) Block out zones via cellular automata
  32.  *      4) Extract the zones
  33.  *      5) Sequence zones
  34.  * parameters: coarseness value 0-5, order (COLUMN or ROW)
  35.  * returns: 1 if OK or 0 if error,  see errno
  36.  ************************************************/
  37. int zone(int coarseness,int order)
  38.     {
  39.     unsigned char *image;
  40.     int dx,dy;
  41.     int samplex,sampley;
  42.     int i;
  43.  
  44.     if (coarseness < 0 || coarseness > 5)
  45.         {               /* test coarseness parameter */
  46.         errno = EINVAL;
  47.         return 0;
  48.         }
  49.                         /* get a scaled copy of the page */
  50.     image = sample_page(&dx,&dy,&samplex,&sampley);
  51.     if (image == NULL)                      /* memory? */
  52.         return 0;
  53. #if CUT_VERTICAL_LINES
  54.     cut_vertical_lines(image,dx,dy);        /* remove boxes around text */
  55. #endif
  56.     block_zones(image,dx,dy,coarseness);    /* block out zones */
  57.     sequence_zones(image,dx,dy,order);
  58.     for (i = 0 ; i < zone_count ; i++)
  59.         {                                   /* translate to full page */
  60.         zone_list[i].x1 *= samplex;
  61.         zone_list[i].y1 *= sampley;
  62.         zone_list[i].x2 *= samplex;
  63.         zone_list[i].y2 *= sampley;
  64.         }
  65.     free(image);                            /* clean up */
  66.     return 1;
  67.     }
  68.  
  69.  
  70. /**************** LOCAL FUNCTIONS ****************/
  71.  
  72. /************************************************
  73.  * function: static unsigned char *sample_page(int *dx,int *dy,int *samplex,int *sampley)
  74.  *  Sample the page.  Normally, the entire page is stored in memory.  Since
  75.  *  the memory requirements are typically a megabyte, the page, in DOS
  76.  *  machines, is somewhere in extended memory.  So that this demo can
  77.  *  work on machines lacking extended memory, I sampled the page when I
  78.  *  scaled it for display.  See display_sample() below.  However, I
  79.  *  have #ifed around the code that is normally used to sample the page
  80.  *  from the memory image.  You need to provide two functions, as well as
  81.  *  the extended memory handler.  They are void memory_info(DISPLAY_BOX *);
  82.  *  which gets the x/y extents of the image, and  (unsigned char *
  83.  *  memory_ptr(int y); which returns a pointer to a scan line in the memory
  84.  *  image.  Sample_page() creates a standardized, reduced image suitable for
  85.  *  cellular automation.  The sample has each byte, not bit, representing a
  86.  *  pixel area.  The byte is 0xff if black or 0x00 if white.
  87.  *  The sampling procedure is important for region finding.  If possible
  88.  *  it should be a function of the density of the original image.  If
  89.  *  the image isn't square, for example a 200x100 fax file, then the
  90.  *  x and y sampling should be adjusted accordingly.  Since I don't
  91.  *  have dpi information here, I am scaling it to a typical, 200dpi,
  92.  *  value after it was adjusted for screen display.
  93.  *  Note: Bit 7 is leftmost and 0 is rightmost; 1 bits are black, 0 are white.
  94.  * parameters: pointers to storage for the byte width and height of the sampled
  95.  *              image and the sample bit distance in x and y
  96.  * returns: pointer to sampled page or NULL if no memory
  97.  ************************************************/
  98. static unsigned char *sample_page(int *dx,int *dy,int *samplex,int *sampley)
  99.     {
  100.     static unsigned char bit_mask[] = {0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};
  101.     unsigned char *image,*line_ptr,*line_ptr2,*buff_ptr;
  102.     DISPLAY_BOX file;
  103.     unsigned int x,y,width,height;
  104.  
  105.     memory_info(&file);     /* need to provide this, gets file dimensions */
  106.                             /* from memory image of file */
  107.     *samplex = SAMPLE_200_X;        /* sample sizes */
  108.     *sampley = SAMPLE_200_Y;
  109.     *dx = file.width / *samplex;    /* extent of sample */
  110.     *dy = file.height / *sampley;
  111.     while (((long)*dx * (long)*dy) > MAX_MALLOC)
  112.         {           /* adjust sampling to fit memory restrictions */
  113.         (*samplex)++;
  114.         (*sampley)++;
  115.         *dx = file.width / *samplex;
  116.         *dy = file.height / *sampley;
  117.         }
  118.     if ((image = malloc(*dx * *dy)) == NULL)    /* allocate sample buffer */
  119.         return NULL;
  120.     memset(image,WHITE,*dx * *dy);          /* set to white */
  121.     width = *dx * *samplex;
  122.     height = *dy * *sampley;
  123.     if (*samplex >= 8)
  124.         {                                   /* byte sampling */
  125.         for (y = 0, buff_ptr = image ; y < height ; y += *sampley)
  126.             {                               /* for each y sample */
  127.                         /* need to provide memory_ptr which gets a pointer
  128.                          * to a scan line from the memory image of the file */
  129.             line_ptr = memory_ptr(y);
  130.             line_ptr2 = memory_ptr(y + *sampley/2); /* double sample in y */
  131.             for (x = 0 ; x < width ; x += *samplex, buff_ptr++)
  132.                 if (*(line_ptr+(x>>3)) | *(line_ptr2+(x>>3)))
  133.                     *buff_ptr = BLACK;  /* if byte has black, set sample */
  134.             }
  135.         }
  136.     else
  137.         {                                   /* bit sampling */
  138.         for (y = 0, buff_ptr = image ; y < height ; y += *sampley)
  139.             {                               /* for each y sample */
  140.                         /* need to provide memory_ptr which gets a pointer
  141.                          * to a scan line from the memory image of the file */
  142.             line_ptr = memory_ptr(y);
  143.             line_ptr2 = memory_ptr(y + *sampley/2); /* double sample in y */
  144.             for (x = 0 ; x < width ; x += *samplex, buff_ptr++)
  145.                 if ((*(line_ptr+(x>>3)) | *(line_ptr2+(x>>3))) & bit_mask[x&7])
  146.                     *buff_ptr = BLACK;      /* if bit is black, set sample */
  147.             }
  148.         }
  149.     return image;
  150.     }
  151.  
  152.  
  153. #if CUT_VERTICAL_LINES
  154. /************************************************
  155.  * function: static void cut_vertical_lines(unsigned char *image,int dx,int dy)
  156.  *  Remove vertical lines from sample.  The purpose of this function is to
  157.  *  unbox text.  Removing the vertical box lines accomplishes this.  Trying
  158.  *  to remove the horizontal lines is dangerous because you might also remove
  159.  *  the text.
  160.  * parameters: pointer to sampled image buffer and x/y extents of buffer
  161.  * returns: nothing
  162.  ************************************************/
  163. static void cut_vertical_lines(unsigned char *image,int dx,int dy)
  164.     {
  165.     int x,y,count,y1;
  166.     unsigned char *ptr,*qtr;
  167.  
  168.     for (x = 0 ; x < dx ; x++)      /* scan image left to right */
  169.         {
  170.         ptr = image+x;
  171.         count = 0;
  172.         for (y = 0 ; y < dy ; y++, ptr += dx)
  173.             {                   /* scan up and down counting line pixels */
  174.             if (*ptr)
  175.                 count++;
  176.             else
  177.                 count = 0;
  178.             if (count >= VERTICAL_LINE_SIZE)
  179.                 {               /* we have a veritcal line */
  180.                 for (y1=y, qtr=ptr ; *ptr!=WHITE && y>=0 ; y--, ptr-=dx)
  181.                     *ptr = WHITE;   /* white out moving up */
  182.                 for (y=y1+1, ptr=qtr+dx ;